package com.frx.leetoffer.dp;

/**
 * Created with IDEA
 * 背包问题 weight{2,2,4,6,3}
 *  n = 5 物品个数
 *  w = 9 物品承受的最大重量   在满足背包最大重量的限制下，背包中物品总重的最大值是多少
 * @author: xrf
 * @Date: 2019/10/31
 * @Time: 14:31
 */
public class TestOne {
    private int max = Integer.MAX_VALUE;
    private int [] weight = {2,2,4,6,3};
    private int n = 5;
    private int w= 9;

    public void solution(int i,int cw){
        // 背包满了，物品都考察完了
        if (cw == w || i == n){
            if (cw > max){
                max = cw;
            }
            return;
        }
        // 选择不装 第i个物品
        solution(i+1,cw);
        if (cw + weight[i] <= w){
            // 选择装第i个物品
            solution(i+1,cw+weight[i]);
        }

    }

}
